package com.dyz.leetcode;

import java.util.Arrays;

public class MaxCoins312 {
    public static void main(String[] args) {
        int [] nums = new int[]{3,1,5,8};
        new MaxCoins312().maxCoins(nums);
    }

    private int[][] dp;

    public void fill(int[] nums, int from, int to) {
        int max = 0, maxLeft, maxRight, result;
        //假设第i个气球是最后被戳破的
        for (int i = from; i <= to; i++) {
            maxLeft = dp[from][i - 1];
            maxRight = dp[i + 1][to];
            result = maxLeft + maxRight + nums[from - 1] * nums[i] * nums[to + 1];
            max = result > max ? result : max;
        }
        dp[from][to] = max;
    }

    public int maxCoins(int[] nums) {
        int length = nums.length;
        dp = new int[length + 2][length + 2];
        for (int i = length + 1; i >= 0; i--) {
            Arrays.fill(dp[i], 0);
        }

        int[] expandNums = new int[length + 2];
        expandNums[0] = expandNums[length + 1] = 1;
        System.arraycopy(nums, 0, expandNums, 1, length);

        for (int span = 0; span < length; span++) {
            //fill a diagonal
            //assume the span (of array of length i) is i-1
            for (int from = length - span; from > 0; from--) {
                //fill dp[from][from + span]
                fill(expandNums, from, from + span);
            }
        }
        return dp[1][length];
    }

}
